In many digital signal processing applications, constraints on local memory sizes necessitate the use of some form of data compression to process the signal. Inherent with effective data compression, however, is a certain degree of data loss. When this loss becomes too great, the resultant compressed data will become unsuitable and unacceptable. However, in the many cases of signal processing where only the general characteristics and behavior of the data are of interest, a compression technique with a known and controlled level of loss may still be acceptable. For example, Ishijama et al. in "Scan-along Polygonal Approximation for Data Compression of Electrocardiograms," IEEE Transactions on Biomedical Engineering, Vol. BME-30, No. 11, pp. 723-729 (1983), show that in processing and storing electrocardiogram (ECG) data, considerable distortion can be tolerated in the approximation of the peak in the so called "PQ" segment. Similarly, others have shown that in many voice-mail applications, using suitable lossy techniques for the compression of the voice signal has negligible effects on the signal quality, and lossy techniques may still be acceptable.
Recently, Imai and Iri in "An Optimal Algorithm for Approximating a Piecewise Linear Function," Journal of Information Processing, Vol. 9, No. 3, pp. 159-162 (1986) and Natarajan and Ruppert in "Sparse Approximation to Curves and Functions," Proc. of the Fourth Canadian Conference on Computational Geometry, St. John's, August 1992, have described an efficient method for compressing waveforms with an acceptable level of loss. Given a specified error, this method approximates data with a piecewise linear function that results in a minimum number of approximation segments. This optimal method in the prior art does not require uniform sampling, and it permits the error to be defined independently at each sample point. These features make this optimal lossy method of compression in the prior art particularly attractive for a large number of signal processing applications.
The basic idea of this prior art compression method is depicted in FIG. 1. The method initially constructs a "tunnel" (110) of radius e (115), the acceptable amount of error deviation, around the original data (120), and proceeds to find the farthest point in the tunnel that is accessible, or "visible," from some point on the left boundary of the tunnel, where the data starts. The portion of the tunnel emanating from this starting point and extending to the farthest point in the tunnel which is still visible from the starting point is defined as a "prefix" (130). Such visibility is computed by drawing lines (122, 124, 126, 128) so that the lines are tangent, if at all, to upper (132, 133, 134) and lower (136, 137, 138) sections of the tunnel (110). These tangents, or "extremal rays" (124), define the longest possible prefixes (130) of the upper and lower envelopes of the tunnel, since these extremal rays represent the extreme directions of visibility. Once determined, the extremal ray (124) in this prefix portion (130) of the tunnel becomes a segment of the approximation of the data in the compression, and the procedure is repeated on the remaining portion of the tunnel; the old prefix section is thereafter "discarded" and a new successive prefix section is found.
The waveform F(x) (120) in the prior art example in FIG. 1, having an error tunnel (110) around it, is approximated as the compressed output G(x) (230) depicted in FIG. 2. Following the flow diagram of FIG. 3, the prior art method optimally compresses the signal F(x) (120, 220) to obtain the compressed signal G(x) (230) in this manner:
1. Construct (301) an error tunnel (210). PA1 2Find (302) a first prefix portion (211) of the tunnel visible from the left boundary of the tunnel by determining the extremal ray of visibility (212) in this portion of the tunnel. PA1 3. Define (303) the extremal ray of visibility (212) as the next line segment in the piecewise linear approximation (230) of the input signal F(x) (220). PA1 4. If the right boundary of the tunnel (240) is visible from the first prefix portion (211), the end of the data is reached and the process is terminated (304, 307). PA1 5. If the right boundary of the tunnel (240) is not visible from the first prefix portion (211), then more data is available; truncate the first prefix portion (211) of the tunnel with the extremal ray (212) and discard the first prefix portion (211) of the tunnel from further consideration; retain and consider (305) the remaining portion (214) of the tunnel following the truncation. PA1 6. Loop back (306) to Step 2, above, and repeat, finding a next prefix portion (215) of the tunnel and defining a new next piecewise linear approximation segment in the process from a next extremal ray of visibility (216). PA1 7. When the final prefix portion of the tunnel (217) includes any portion of the right boundary (240), the process can be terminated.
For a specified error, e, in this prior art compression technique, the number of points, or approximation segments, can be shown to be always optimal. The error can be set independently at each sample point, and the technique does not require uniform sampling or specific knowledge of the characteristics of the source. These features make this prior art compression method particularly suitable for a large number of applications.
Many applications, such as the continuous monitoring, transmission, and storage of ECG data of an ambulatory heart patient's heart functions, however, require compression techniques to operate in real time. Furthermore, the compression requirement for this heart patient extends to suitably simple compression hardware which must be sufficiently rugged and portable to reliably accompany the heart monitoring device the heart patient may be carrying.
Even though the above-described prior art compression method operates linearly with a given number of samples, its arithmetic processing becomes prohibitively complex for real time operation on a general purpose processor. The novel compression method according to the present invention greatly simplifies the prior art compression method and, in doing so, allows real time operation without the need for special purpose processors. The novel compression invention, because of its simplification, additionally facilitates implementation of the novel compression technique on a single integrated semiconductor chip. The resultant hardware, then, is simple and portable. Although the simplified compression method in accordance with the preferred embodiment of the invention is no longer optimal, the number of segments in the resultant piecewise approximation of a signal from this method nevertheless is generally a factor of 1.5 of the minimum number resulting from the earlier described optimal compression method in the prior art.